


#include <iostream>
using namespace std;


 struct ListNode 
 {
 	int val;
 	struct ListNode *next;

    ListNode(int val)
        : val(val)
        , next(nullptr)
    {

    }
 };

 typedef struct ListNode SLNode;

 SLNode* CreateSList()
 {
     /*SLNode* node1 = new SLNode(1);
     SLNode* node2 = new SLNode(2);
     SLNode* node3 = new SLNode(3);
     SLNode* node4 = new SLNode(4);
     SLNode* node5 = new SLNode(5);

     node1->next = node2;
     node2->next = node3;
     node3->next = node4;
     node4->next = node5;*/

     /*SLNode* node1 = new SLNode(3);
     SLNode* node2 = new SLNode(5);
     node1->next = node2;*/

   /* SLNode* node1 = new SLNode(1);
    SLNode* node2 = new SLNode(2);
    SLNode* node3 = new SLNode(-3);
    SLNode* node4 = new SLNode(3);
    SLNode* node5 = new SLNode(1);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;*/

    SLNode* node1 = new SLNode(0);
    SLNode* node2 = new SLNode(0);
    node1->next = node2;

     return node1;
 }

 struct ListNode* reverseBetween1(struct ListNode* head, int m, int n)
 {
     typedef struct ListNode SLNode;

     if (m == n)
     {
         return head;
     }
     else
     {
         SLNode* left = head, * right = head;
         SLNode* prev = head, * pnext = head;

         int cnt = 1;
         SLNode* cur = head;
         while (cnt < m)
         {
             prev = cur;
             cur = cur->next;
             ++cnt;
         }
         left = prev;

         while (cnt < n)
         {
             cur = cur->next;
             ++cnt;
         }
         right = cur->next;

         prev = right;
         cur = left->next;
         while (cur != right)
         {
             pnext = cur->next;
             cur->next = prev;
             prev = cur;
             cur = pnext;
         }
         left->next = prev;

         return head;
     }
 }

#include <assert.h>
typedef struct ListNode SLNode;

SLNode* GetNode(int val)
{
    SLNode* tmp = (SLNode*)malloc(sizeof(SLNode));
    assert(tmp);

    tmp->val = val;
    tmp->next = NULL;

    return tmp;
}

SLNode* _reverseBetween(SLNode* head, SLNode* tail)
{
    SLNode* guard = GetNode(0), * gnext = NULL;
    SLNode* cur = head, * cnext = NULL;
    SLNode* end = tail->next;

    while (cur != end)
    {
        cnext = cur->next;

        cur->next = gnext;
        guard->next = cur;

        gnext = guard->next;
        cur = cnext;
    }

    SLNode* res = guard->next;
    free(guard);
    guard = NULL;

    return res;
}

struct ListNode* reverseBetween2(struct ListNode* head, int m, int n)
{
    SLNode* cur = head;
    SLNode* phead = head, * ptail = head;
    SLNode* left = head, * right = head;

    int cnt = 0;
    while (cnt < m - 1)
    {
        left = cur;
        cur = cur->next;
        ++cnt;
    }
    phead = cur;

    while (cnt < n - 1)
    {
        cur = cur->next;
        ++cnt;
    }
    ptail = cur;
    right = cur->next;

    if (phead == head)
        head = _reverseBetween(phead, ptail);
    else
        left->next = _reverseBetween(phead, ptail);

    phead->next = right;

    return head;
}

struct ListNode* reverseBetween3(struct ListNode* head, int m, int n)
{
    typedef struct ListNode SLNode;

    if (m == n)
        return head;

    SLNode* guard = (SLNode*)malloc(sizeof(SLNode));
    guard->next = head;
    SLNode* prev = guard;

    int i;
    for (i = 1; i < m; i++)
    {
        prev = prev->next;
    }

    SLNode* cur = prev->next;
    for (i = m; i < n; i++)
    {
        SLNode* next = cur->next;
        cur->next = next->next;

        next->next = prev->next;
        prev->next = next;
    }

    SLNode* res = guard->next;
    free(guard);
    guard = NULL;

    return res;
}

void Test1(void)
{
    int m = 1, n = 2;
    SLNode* head = CreateSList();

    reverseBetween1(head, m, n);
    //reverseBetween2(head, m, n);

}

struct ListNode* removeZeroSumSublists(struct ListNode* head)
{
    typedef struct ListNode SLNode;

    SLNode* guard = (SLNode*)malloc(sizeof(SLNode));
    guard->next = head;

    SLNode* cur = guard;
    while (cur)
    {
        int sum = 0;
        SLNode* ccur = cur->next;

        while (ccur)
        {
            sum += ccur->val;
            if (0 == sum)
            {
                cur->next = ccur->next;

                SLNode* del = cur->next;
                while (del != ccur->next)
                {
                    SLNode* next = del->next;
                    free(del);
                    del = NULL;
                    del = next;
                }
            }

            ccur = ccur->next;
        }

        cur = cur->next;
    }

    head = guard->next;
    free(guard);
    guard = NULL;

    return head;
}
void Test2(void)
{
    SLNode* node = CreateSList();

    removeZeroSumSublists(node);
}

int main()
{
    //Test1();
    Test2();


	return 0;
}